package leetcode.weekly.week292;

//Solution4Test
public class Solution4 {
	int m, n;

	public boolean hasValidPath(char[][] grid) {
		m = grid.length;
		n = grid[0].length;
		if (grid[m - 1][n - 1] == '(' || grid[0][0] == ')') {
			return false;
		}
		Boolean[][][] dp = new Boolean[m][n][m + n];
		return this.hasValidPath(grid, 0, 0, 0, dp);
	}

	private boolean hasValidPath(char[][] grid, int x, int y, int k, Boolean[][][] dp) {
		if (k < 0) {
			return false;
		}
		if (x == m - 1 && y == n - 1) {
			return k == 1;
		}
		if (dp[x][y][k] != null) {
			return dp[x][y][k];
		}
		char cur = grid[x][y];
		if (cur == ')' && k == 0) {
			dp[x][y][k] = false;
			return false;
		}
		int nextk = cur == '(' ? k + 1 : k - 1;
		if (x + 1 < m) {
			if (this.hasValidPath(grid, x + 1, y, nextk, dp)) {
				return true;
			}
		}
		if (y + 1 < n) {
			if (this.hasValidPath(grid, x, y + 1, nextk, dp)) {
				return true;
			}
		}
		dp[x][y][k] = false;
		return false;
	}

}
